Maximum sum circular subarray [Kadane, NextArray, PrefixSum+Monoqueue]¶
Time: O(N); Space: O(1); medium
Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)
Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
Example 1:
Input: A = [1, -2, 3, -2]
Output: 3
Explanation:
Subarray [3] has maximum sum 3.
Example 2:
Input: A = [5, -3, 5]
Output: 10
Explanation:
Subarray [5, 5] has maximum sum 5 + 5 = 10.
Example 3:
Input: A = [3, -1, 2, -1]
Output: 4
Explanation:
Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4.
Example 4:
Input: A = [3, -2, 2, -3]
Output: 3
Explanation:
Subarray [3] and [3,-2,2] both have maximum sum 3.
Example 5:
Input: A = [-2,-3,-1]
Output: -1
Explanation:
Subarray [-1] has maximum sum -1.
Notes:
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
Intuition and Algorithm Subarrays of circular arrays can be classified as either as one-interval subarrays, or two-interval subarrays, depending on how many intervals of the fixed-size buffer A are required to represent them.
For example, if A = [0, 1, 2, 3, 4, 5, 6] is the underlying buffer of our circular array, we could represent the subarray [2, 3, 4] as one interval [2, 4], but we would represent the subarray [5, 6, 0, 1] as two intervals [5, 6], [0, 1].
Using Kadane’s algorithm, we know how to get the maximum of one-interval subarrays, so it only remains to consider two-interval subarrays.
Let’s say the intervals are [0,i], [j,A.length−1]. Let’s try to compute the i-th candidate: the largest possible sum of a two-interval subarray for a given ii. Computing the [0,i] part of the sum is easy. Let’s write Tj = A[j] + A[j+1] + … + A[A.length - 1] and Rj = max(Tk), k>= j so that the desired i-th candidate is: (A[0] + A[1] + … + A[i]) + Ri+2
Since we can compute Tj and Rj in linear time, the answer is straightforward after this setup.
[13]:
import sys
class Solution1(object):
"""
Notes and A Primer on Kadane's Algorithm
"""
def maxSubarraySumCircular(self, A) -> int:
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
# Kadane's algorithm
result = cur = -sys.maxsize - 1
for x in A:
cur = x + max(cur, 0)
result = max(result, cur)
# return result
# result is the answer for 1-interval subarrays.
# Now, let's consider all 2-interval subarrays.
# For each i, we want to know
# the maximum of sum(A[j:]) with j >= i+2
# rightsums[i] = sum(A[i:])
rightsums = [None] * N
rightsums[-1] = A[-1]
for i in range(N-2, -1, -1):
rightsums[i] = rightsums[i+1] + A[i]
# maxright[i] = max_{j >= i} rightsums[j]
maxright = [None] * N
maxright[-1] = rightsums[-1]
for i in range(N-2, -1, -1):
maxright[i] = max(maxright[i+1], rightsums[i])
leftsum = 0
for i in range(N-2):
leftsum += A[i]
result = max(result, leftsum + maxright[i+2])
return result
[14]:
s = Solution1()
A = [1,-2,3,-2]
assert s.maxSubarraySumCircular(A) == 3
A = [5,-3,5]
assert s.maxSubarraySumCircular(A) == 10
A = [3,-1,2,-1]
assert s.maxSubarraySumCircular(A) == 4
A = [3,-2,2,-3]
assert s.maxSubarraySumCircular(A) == 3
A = [-2,-3,-1]
assert s.maxSubarraySumCircular(A) == -1
Next Array¶
Intuition and Algorithm Subarrays of circular arrays can be classified as either as one-interval subarrays, or two-interval subarrays, depending on how many intervals of the fixed-size buffer A are required to represent them. For example, if A = [0, 1, 2, 3, 4, 5, 6] is the underlying buffer of our circular array, we could represent the subarray [2, 3, 4] as one interval [2, 4], but we would represent the subarray [5, 6, 0, 1] as two intervals [5, 6], [0, 1]. Using Kadane’s algorithm, we know how to get the maximum of one-interval subarrays, so it only remains to consider two-interval subarrays.
Let’s say the intervals are [0, i], [j, A.length - 1]. Let’s try to compute the i-th candidate: the largest possible sum of a two-interval subarray for a given i. Computing the [0, i] part of the sum is easy. Let’s write Tj = A[j] + A[j+1] + … + A[A.length - 1] and Rj = max(Tk), k >= j so that the desired i-th candidate is: (A[0] + A[1] + … + A[i]) + Ri+2 Since we can compute Tj and Rj in linear time, the answer is straightforward after this setup.
[29]:
class Solution2(object):
"""
Next Array
Time: O(N)
Space: O(N)
"""
def maxSubarraySumCircular(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
ans = cur = -sys.maxsize - 1
for x in A:
cur = x + max(cur, 0)
ans = max(ans, cur)
# ans is the answer for 1-interval subarrays.
# Now, let's consider all 2-interval subarrays.
# For each i, we want to know
# the maximum of sum(A[j:]) with j >= i+2
# rightsums[i] = sum(A[i:])
rightsums = [None] * N
rightsums[-1] = A[-1]
for i in range(N-2, -1, -1):
rightsums[i] = rightsums[i+1] + A[i]
# maxright[i] = max_{j >= i} rightsums[j]
maxright = [None] * N
maxright[-1] = rightsums[-1]
for i in range(N-2, -1, -1):
maxright[i] = max(maxright[i+1], rightsums[i])
leftsum = 0
for i in range(N-2):
leftsum += A[i]
ans = max(ans, leftsum + maxright[i+2])
return ans
[30]:
s = Solution2()
A = [1,-2,3,-2]
assert s.maxSubarraySumCircular(A) == 3
A = [5,-3,5]
assert s.maxSubarraySumCircular(A) == 10
A = [3,-1,2,-1]
assert s.maxSubarraySumCircular(A) == 4
A = [3,-2,2,-3]
assert s.maxSubarraySumCircular(A) == 3
A = [-2,-3,-1]
assert s.maxSubarraySumCircular(A) == -1
Prefix Sums + Monoqueue¶
Intuition First, we can frame the problem as a problem on a fixed array. We can consider any subarray of the circular array with buffer A, to be a subarray of the fixed array A + A. For example, if A = [0,1,2,3,4,5] represents a circular array, then the subarray [4,5,0,1] is also a subarray of fixed array [0,1,2,3,4,5,0,1,2,3,4,5]. Let B = A + A be this fixed array. Now say N = A.length, and consider the prefix sums Pk = B[0] + B[1] + … + B[k-1] Then, we want the largest Pj - Pi, where j - i <= N.
Now, consider the j-th candidate answer: the best possible Pj - Pi for a fixed j. We want the i so that Pi is smallest, with j - N <= i <= j. Let’s call this the optimal i for the j-th candidate answer. We can use a monoqueue to manage this.
Algorithm Iterate forwards through j, computing the j-th candidate answer at each step. We’ll maintain a queue of potentially optimal i’s. The main idea is that if i1 < i2 and Pi1 >= Pi2, then we don’t need to remember i1 anymore. Please see the inline comments for more algorithmic details about managing the queue.
[31]:
import collections
class Solution3(object):
"""
Prefix Sums + Monoqueue
Time: O(N)
Space: O(N)
"""
def maxSubarraySumCircular(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
# Compute P[j] = sum(B[:j]) for the fixed array B = A+A
P = [0]
for _ in range(2):
for x in A:
P.append(P[-1] + x)
# Want largest P[j] - P[i] with 1 <= j-i <= N
# For each j, want smallest P[i] with i >= j-N
ans = A[0]
deque = collections.deque([0]) # i's, increasing by P[i]
for j in range(1, len(P)):
# If the smallest i is too small, remove it.
if deque[0] < j-N:
deque.popleft()
# The optimal i is deque[0], for cand. answer P[j] - P[i].
ans = max(ans, P[j] - P[deque[0]])
# Remove any i1's with P[i2] <= P[i1].
while deque and P[j] <= P[deque[-1]]:
deque.pop()
deque.append(j)
return ans
[32]:
s = Solution3()
A = [1,-2,3,-2]
assert s.maxSubarraySumCircular(A) == 3
A = [5,-3,5]
assert s.maxSubarraySumCircular(A) == 10
A = [3,-1,2,-1]
assert s.maxSubarraySumCircular(A) == 4
A = [3,-2,2,-3]
assert s.maxSubarraySumCircular(A) == 3
A = [-2,-3,-1]
assert s.maxSubarraySumCircular(A) == -1
Kadane’s (Sign Variant)¶
Intuition and Algorithm As in Kadane’s algorithm, subarrays of circular arrays can be classified as either as one-interval subarrays, or two-interval subarrays. Using Kadane’s algorithm kadane for finding the maximum sum of non-empty subarrays, the answer for one-interval subarrays is kadane(A). Now, let N = A.length. For a two-interval subarray like: (A0 + A1 + … + Ai) + (Aj + Aj+1 + …+ AN-1 we can write this as
sum(Ak) - (Ai+1 + Ai+2 + … + Aj-1}, 0 <= k <= N-1.
For two-interval subarrays, let B be the array A with each element multiplied by −1. Then the answer for two-interval subarrays is sum(A) + kadane(B). Except, this isn’t quite true, as if the subarray of B we choose is the entire array, the resulting two interval subarray [0, i] + [j, N-1] would be empty. We can remedy this problem by doing Kadane twice: * once on B with the first element removed, and * once on B with the last element removed.
[33]:
class Solution4(object):
"""
Kadane's (Sign Variant)
Time: O(N)
Space: O(1)
"""
def maxSubarraySumCircular(self, A):
"""
:type A: List[int]
:rtype: int
"""
def kadane(gen):
# Maximum non-empty subarray sum
ans = cur = -sys.maxsize - 1
for x in gen:
cur = x + max(cur, 0)
ans = max(ans, cur)
return ans
S = sum(A)
ans1 = kadane(iter(A))
ans2 = S + kadane(-A[i] for i in range(1, len(A)))
ans3 = S + kadane(-A[i] for i in range(len(A) - 1))
return max(ans1, ans2, ans3)
[34]:
s = Solution4()
A = [1,-2,3,-2]
assert s.maxSubarraySumCircular(A) == 3
A = [5,-3,5]
assert s.maxSubarraySumCircular(A) == 10
A = [3,-1,2,-1]
assert s.maxSubarraySumCircular(A) == 4
A = [3,-2,2,-3]
assert s.maxSubarraySumCircular(A) == 3
A = [-2,-3,-1]
assert s.maxSubarraySumCircular(A) == -1